/*
 * Copyright (c) 2021
 * User:LENOVO
 * File:合并K个升序链表.java
 * Date:2021/02/18 14:20:18
 */

package org.bytedance.链表和数;

import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.stream.Collectors;

/**
 * 给你一个链表数组，每个链表都已经按升序排列。
 * <p>
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 * <p>
 * 输入: lists = [[1,4,5],[1,3,4],[2,6]]
 * 输出：[1,1,2,3,4,4,5,6]
 * <p>
 * <p>
 * 输入：lists = []
 * 输出：[]
 * <p>
 * <p>
 * 输入：lists = [[]]
 * 输出：[]
 */
public class 合并K个升序链表 {


    private static class ListNode {
        int value;
        ListNode next;

        public ListNode() {
        }

        public ListNode(int value) {
            this.value = value;
        }
    }

    public static void main(String[] args) {
        合并K个升序链表 instance = new 合并K个升序链表();
        ListNode[] listNodes = new ListNode[]{
                instance.build(1, 4, 5),
                instance.build(1, 3, 4),
                instance.build(2, 6)
        };

        ListNode listNode = instance.mergeLists(listNodes);
        instance.printList(listNode);





        // input list=[]
        listNodes = new ListNode[0];
        listNode = instance.mergeLists(listNodes);
        instance.printList(listNode);

        listNodes = new ListNode[]{
                instance.build(1, 4, 5),
                instance.build(1, 3, 4),
                instance.build(2, 6)
        };
        ListNode listNode1 = instance.mergeLists2(listNodes);
        instance.printList(listNode1);

        listNodes = new ListNode[]{
                instance.build(1, 4, 5),
                instance.build(1, 3, 4),
                instance.build(2, 6)
        };

        listNode1 = instance.mergeLists改良(listNodes);
        instance.printList(listNode1);
    }

    private void printList(ListNode head) {
        StringBuilder sb = new StringBuilder();
        while (head != null) {
            sb.append(head.value).append(" ");
            head = head.next;
        }
        System.out.println(sb.toString());
    }

    private ListNode[] build(List<int[]> inputs) {
        if (inputs == null || inputs.isEmpty()) return null;
        List<int[]> collect = inputs.stream().filter(item -> item.length > 0).collect(Collectors.toList());
        ListNode[] listNodes = new ListNode[collect.size()];
        for (int i = 0; i < collect.size(); i++) {
            listNodes[i] = build(collect.get(i));
        }
        return listNodes;
    }

    private ListNode build(int[] ints) {
        if (ints == null || ints.length == 0) return null;
        ListNode head = null, cur = null;
        for (int i = 0; i < ints.length; i++) {
            if (head == null) {
                head = new ListNode(ints[i]);
                cur = head;
            } else {
                cur.next = new ListNode(ints[i]);
                cur = cur.next;
            }
        }
        return head;
    }

    private ListNode build(Integer... ints) {
        if (ints == null || ints.length == 0) return null;
        ListNode head = null, cur = null;
        for (int i = 0; i < ints.length; i++) {
            if (head == null) {
                head = new ListNode(ints[i]);
                cur = head;
            } else {
                cur.next = new ListNode(ints[i]);
                cur = cur.next;
            }
        }
        return head;
    }

    /**
     * 使用优先级队列
     */
    public ListNode mergeLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        PriorityQueue<ListNode> priorityQueue = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.value - o2.value;
            }
        });
        ListNode mergeNode = new ListNode(Integer.MIN_VALUE);
        ListNode node = mergeNode;
        for (ListNode item : lists) {
            if (item != null) priorityQueue.add(item);
        }
        while (!priorityQueue.isEmpty()) {
            ListNode poll = priorityQueue.poll();
            node.next = poll;
            node = node.next;
            if (poll.next != null) priorityQueue.offer(poll.next);
        }
        return mergeNode;
    }

    /**
     * 使用优先级队列
     */
    public ListNode mergeLists改良(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        PriorityQueue<ListNode> priorityQueue = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.value - o2.value;
            }
        });
        ListNode mergeNode = null, node = null;
        for (ListNode item : lists) {
            if (item != null) priorityQueue.add(item);
        }
        while (!priorityQueue.isEmpty()) {
            ListNode poll = priorityQueue.poll();
            if (mergeNode == null) {
                mergeNode = poll;
                node = poll;
            } else {
                node.next = poll;
                node = node.next;
            }
            if (poll.next != null) priorityQueue.offer(poll.next);
        }
        return mergeNode;
    }

    /**
     * 使用两两合并
     */
    public ListNode mergeLists2(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        return merge(lists, 0, lists.length - 1);

    }

    private ListNode merge(ListNode[] lists, int left, int right) {
        if (left == right) return lists[left];
        int mid = left + ((right - left) >> 1);
        ListNode l1 = merge(lists, left, mid);
        ListNode l2 = merge(lists, mid + 1, right);
        return mergeTwo(l1, l2);
    }

    private ListNode mergeTwo(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.value < l2.value) {
            l1.next = mergeTwo(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwo(l1, l2.next);
            return l2;
        }
    }
}
